﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Algorithms
{
    /// <summary>
    /// Summary description for TraversalMethods.
    /// </summary>
    public enum TraversalMethods
    {
        Preorder,
        Inorder,
        Postorder
    }

    class NodeState
    {
        private Point2D point;
        private double currentDistance;
        public NodeState(Point2D pt, double distance)
        {
            this.point = pt;
            this.currentDistance = distance;
        }

        public double getDistance()
        {
            return this.currentDistance;
        }

        public Point2D getPoint()
        {
            return this.point;
        }


    }

    public class KdTree
    {
        /**
        * the root of the KD tree
        */
        private KdTreeNode<Point2D> root = null;

        /**
         * number of points in the set.
         */
        private int count = 0;


        /**
         * construct an empty set of points
         */
        public KdTree()
        {
            //
        }

        /**
         * is the set empty?
         * 
         * @return bool
         */
        public bool isEmpty()
        {
            return size() == 0;
        }

        /**
         * number of points in the set.
         * 
         * @return Integer
         */
        public int size()
        {
            return count;
        }

        /**
         * add the point p to the set (if it is not already in the set). The
         * algorithms for search and insert are similar to those for BSTs, but at
         * the root we use the x-coordinate (if the point to be inserted has a
         * smaller x-coordinate than the point at the root, go left; otherwise go
         * right); then at the next level, we use the y-coordinate (if the point to
         * be inserted has a smaller y-coordinate than the point in the node, go
         * left; otherwise go right); then at the next level the x-coordinate, and
         * so forth.
         * 
         * @param p
         *            input
         */
        public void Insert(Point2D p)
        {
            if (p == null)
            {
                throw new ArgumentNullException();
            }

            double x = p.x();
            double y = p.y();

            double result = 0;
            bool isVerticalLine = true;
            // now, insert n into the tree
            // trace down the tree until we hit a NULL
            KdTreeNode<Point2D> current = root, parent = null;
            while (current != null)
            {
                double dx = x - current.getValue().x();
                double dy = y - current.getValue().y();
                if (isVerticalLine)
                {
                    result = dx;
                }
                else
                {
                    result = dy;
                }

                if (dx == 0 && dy == 0)
                {
                    // they are equal - inserting a duplicate - do nothing
                    return;
                }
                else if (result <= 0)
                {
                    // current.Value > n.Value
                    // therefore, n must be added to current's left subtree
                    parent = current;
                    current = current.getLeft();
                }
                else
                {
                    // current.Value < n.Value
                    // therefore, n must be added to current's right subtree
                    parent = current;
                    current = current.getRight();
                }
                isVerticalLine = !isVerticalLine;
            }

            // first, create a new Node
            KdTreeNode<Point2D> n = new KdTreeNode<Point2D>(p);
            n.setVerticalLine(isVerticalLine);

            // at this point we have reached the end of the tree
            ++count;
            if (parent == null)
            {
                // the tree was empty
                root = n;
                n.setRectangle(createRectangle(true, true, null));
            }
            else
            {
                if (!isVerticalLine)
                {
                    result = x - parent.getValue().x();
                }
                else
                {
                    result = y - parent.getValue().y();
                }

                if (result <= 0)
                {
                    // parent.Value < n.Value
                    // therefore, n must be added to parent's left subtree
                    parent.setLeft(n);
                    n.setRectangle(createRectangle(isVerticalLine, true, parent));
                }
                else
                {
                    // parent.Value < n.Value
                    // therefore, n must be added to parent's right subtree
                    parent.setRight(n);
                    n.setRectangle(createRectangle(isVerticalLine, false, parent));
                }
            }
        }

        /**
    * create Rectangle of the point.
    * 
    * @param isVerticalLine
    *            input
    * @param isLeftChild
    *            input
    * @param parent
    *            input
    * @return RectHV
    */
        private RectHV createRectangle(bool isVerticalLine, bool isLeftChild,
                KdTreeNode<Point2D> parent)
        {
            const double xaxis = 1.0;
            const double yaxis = 1.0;

            double xMin = 0;
            double yMin = 0;
            double xMax = xaxis;
            double yMax = yaxis;

            if (parent != null)
            {
                if (!isVerticalLine)
                {
                    yMin = parent.getRectangle().ymin();
                    yMax = parent.getRectangle().ymax();
                    if (isLeftChild)
                    {
                        // this node is not vertical point.
                        xMin = parent.getRectangle().xmin();
                        xMax = parent.getValue().x();
                    }
                    else
                    {
                        xMin = parent.getValue().x();
                        xMax = parent.getRectangle().xmax();
                    }
                }
                else
                {
                    xMin = parent.getRectangle().xmin();
                    xMax = parent.getRectangle().xmax();
                    if (isLeftChild)
                    {
                        yMin = parent.getRectangle().ymin();
                        yMax = parent.getValue().y();
                    }
                    else
                    {
                        yMin = parent.getValue().y();
                        yMax = parent.getRectangle().ymax();
                    }
                }
            }
            return new RectHV(xMin, yMin, xMax, yMax);
        }

        /**
         * does the set contain the point p?
         * 
         * @param p
         *            input
         * @return bool
         */
        public bool contains(Point2D p)
        {
            if (p == null)
            {
                throw new ArgumentNullException();
            }

            return SearchHelper(root, p) != null;
        }

        private KdTreeNode<Point2D> SearchHelper(KdTreeNode<Point2D> current, Point2D data)
        {
            if (current == null)
            {
                return null; // node was not found
            }
            else
            {
                int result = current.getValue().CompareTo(data);
                if (result == 0)
                {
                    // they are equal - we found the data
                    return current;
                }
                else
                {
                    double dx = data.x() - current.getValue().x();
                    double dy = data.y() - current.getValue().y();
                    double cmp = 0;

                    if (current.isVerticalLine())
                    {
                        cmp = dx;
                    }
                    else
                    {
                        cmp = dy;
                    }

                    if (cmp <= 0)
                    {
                        return SearchHelper(current.getLeft(), data);
                    }
                    else
                    {
                        return SearchHelper(current.getRight(), data);
                    }
                }

            }
        }


        /**
         * dump the contents of the BST's Inorder traversal into an ArrayList and
         * then return this ArrayList's enumerator
         * 
         * @return ArrayList
         */
        private List<KdTreeNode<Point2D>> iterator()
        {
            List<KdTreeNode<Point2D>> contents = new List<KdTreeNode<Point2D>>();
            InorderTraversalBuildup(root, contents);
            return contents;
        }

        /**
         * Inorder Traversal Buildup
         * 
         * @param current
         *            input
         * @param contents
         *            input
         */
        private void InorderTraversalBuildup(KdTreeNode<Point2D> current,
                List<KdTreeNode<Point2D>> contents)
        {
            if (current != null)
            {
                InorderTraversalBuildup(current.getLeft(), contents);
                contents.Add(current);
                InorderTraversalBuildup(current.getRight(), contents);
            }
        }

        /**
         * all points in the set that are inside the rectangle.
         * 
         * @param rect
         *            input
         * @return Iterable<Point2D>
         */
        public IEnumerable<Point2D> range(RectHV rect)
        {
            List<Point2D> contents = new List<Point2D>();
            searchWithRange(
                rect.xmin(),
                rect.ymin(),
                rect.xmax(),
                rect.ymax(),
                root, contents);
            return contents;
        }

        /**
         * search With Region scope
         * 
         * @param rect
         * @param current
         * @param contents
         */
        private void searchWithRange(
            double xmin, 
            double ymin, 
            double xmax, 
            double ymax, 
            KdTreeNode<Point2D> current,
            List<Point2D> contents)
        {

            if (current != null)
            {
                Point2D p = current.Value;
                double x = p.x();
                double y = p.y();

                if (x <= xmax && p.x() >= xmin
                        && p.y() <= ymax && p.y() >= ymin)
                {
                    contents.Add(p);
                }

                bool isVertical = current.isVerticalLine();
                bool goLeft = true;
                bool goRight = true;
                if (isVertical)
                {
                    if (x < xmin)
                    {
                        goLeft = false;
                    }
                    if (x > xmax)
                    {
                        goRight = false;
                    }
                }
                else
                {
                    if (y < ymin)
                    {
                        goLeft = false;
                    }

                    if (y > ymax)
                    {
                        goRight = false;
                    }
                }

                if (goLeft)
                {
                    // can search left;
                    searchWithRange(xmin, ymin, xmax, ymax, current.getLeft(), contents);
                }

                if (goRight)
                {
                    // can search right;
                    searchWithRange(xmin, ymin, xmax, ymax, current.getRight(), contents);
                }

            }
        }

        /**
         * Nearest neighbor search. *
         * 
         * @param p
         * @return Point2D
         */
        public Point2D nearest(Point2D p)
        {
            // a nearest neighbor in the set to p; null if set is empty.
            if (isEmpty())
            {
                return null;
            }
            else
            {
                NodeState nearestNeighbor = new NodeState(root.getValue(),
                   Double.MaxValue);

                nearestNeighbor = searchNearestNeighbor(p.x(), p.y(), p, root,
                        nearestNeighbor);

                return nearestNeighbor.getPoint();
            }
        }



        /**
         * To find a closest point to a given query point, start at the root and
         * recursively search in both subtrees using the following pruning rule: if
         * the closest point discovered so far is closer than the distance between
         * the query point and the rectangle corresponding to a node, there is no
         * need to explore that node (or its subtrees). That is, a node is searched
         * only if it might contain a point that is closer than the best one found
         * so far. The effectiveness of the pruning rule depends on quickly finding
         * a nearby point. To do this, organize your recursive method so that when
         * there are two possible subtrees to go down, you always choose the subtree
         * that is on the same side of the splitting line as the query point as the
         * first subtree to explore—the closest point found while exploring the
         * first subtree may enable pruning of the second subtree.
         * 
         * @param p
         *            input
         * @param current
         *            input
         * @param distance
         *            input
         * @return input
         */
        private NodeState searchNearestNeighbor(
                double targetX,
                double targetY, 
                Point2D pt,
                KdTreeNode<Point2D> current, 
                NodeState closestNode)
        {

            NodeState nearestNeighbor = closestNode;

            if (current != null)
            {

                double x = current.getValue().x();
                double y = current.getValue().y();

                double pivotToTarget = euclideanDistance(x, y, targetX, targetY);
                double currentDistance = nearestNeighbor.getDistance();

                if (pivotToTarget < currentDistance)
                {
                    // update the record
                    nearestNeighbor = new NodeState(current.getValue(), pivotToTarget);
                }

                RectHV rect = current.getRectangle();
                if (!rect.contains(pt)
                        && currentDistance < rect.distanceSquaredTo(pt))
                {
                    return nearestNeighbor;
                }

                bool goLeftFirst = false;

                if (current.isVerticalLine())
                {
                    goLeftFirst = (targetX - x <= 0);
                }
                else
                {
                    goLeftFirst = (targetY - y <= 0);
                }

                if (goLeftFirst)
                {
                    nearestNeighbor = searchNearestNeighbor(targetX, targetY, pt,
                            current.getLeft(), nearestNeighbor);
                    nearestNeighbor = searchNearestNeighbor(targetX, targetY, pt,
                            current.getRight(), nearestNeighbor);
                }
                else
                {
                    nearestNeighbor = searchNearestNeighbor(targetX, targetY, pt,
                            current.getRight(), nearestNeighbor);
                    nearestNeighbor = searchNearestNeighbor(targetX, targetY, pt,
                            current.getLeft(), nearestNeighbor);
                }
            }

            return nearestNeighbor;
        }

        /**
         * calculate Euclidean Distance
         * 
         * @param p1
         *            point 1
         * @param p2
         *            point 2
         * @return double
         */
        private double euclideanDistance(Point2D p1, Point2D p2)
        {
            //return euclideanDistance(p1.x(), p1
            double diffX = p1.x() - p2.x();
            double diffY = p1.y() - p2.y();
            return diffX * diffX + diffY * diffY;
        }

        private double euclideanDistance(double x0, double y0, double x1, double y1)
        {
            double diffX = x0 - x1;
            double diffY = y0 - y1;
            return diffX * diffX + diffY * diffY;
        }

        #region Traversal Methods

        public override string ToString()
        {
            return ToString(TraversalMethods.Preorder);
        }

        public virtual string ToString(TraversalMethods traversalMethod)
        {
            return ToString(traversalMethod, "\r\n");
        }

        public virtual string ToString(TraversalMethods traversalMethod, string separator)
        {
            string results = String.Empty;
            switch (traversalMethod)
            {
                case TraversalMethods.Preorder:
                    results = PreorderTraversal(root, separator);
                    break;

                case TraversalMethods.Inorder:
                    results = InorderTraversal(root, separator);
                    break;

                case TraversalMethods.Postorder:
                    results = PostorderTraversal(root, separator);
                    break;
            }

            // finally, hack off the last separator
            if (results.Length == 0)
                return String.Empty;
            else
                return results.Substring(0, results.Length - separator.Length);
        }

        #region Pre-order

        protected virtual string PreorderTraversal(KdTreeNode<Point2D> current, string separator)
        {
            if (current != null)
            {
                StringBuilder sb = new StringBuilder();
                sb.Append(current.ToString());
                sb.Append(separator);

                sb.Append(PreorderTraversal(current.LeftChild, separator));
                sb.Append(PreorderTraversal(current.RightChild, separator));
                return sb.ToString();
            }
            else
                return String.Empty;
        }
        #endregion

        #region In-order
        protected virtual string InorderTraversal(KdTreeNode<Point2D> current, string separator)
        {
            if (current != null)
            {
                StringBuilder sb = new StringBuilder();
                sb.Append(InorderTraversal(current.LeftChild, separator));
                sb.Append(current.ToString());
                sb.Append(separator);
                sb.Append(InorderTraversal(current.RightChild, separator));
                return sb.ToString();
            }
            else
                return String.Empty;
        }
        #endregion

        #region Post-order
        protected virtual string PostorderTraversal(KdTreeNode<Point2D> current, string separator)
        {
            if (current != null)
            {
                StringBuilder sb = new StringBuilder();
                sb.Append(PostorderTraversal(current.LeftChild, separator));
                sb.Append(PostorderTraversal(current.RightChild, separator));

                sb.Append(current.ToString());
                sb.Append(separator);
                return sb.ToString();
            }
            else
                return String.Empty;
        }
        #endregion
        #endregion

    }
}